package com.leetcode.partition10;

import java.io.*;

/**
 * @author `RKC`
 * @date 2022/1/4 11:50
 */
public class LC913猫和老鼠 {

    private static int N = 55, n = 0;
    //dp[k][i][j]表示当前进行了k步，老鼠所在的位置是i节点，猫所在的位置是j节点，最终获胜的情况（0：平局，1：老鼠胜，2：猫胜）
    private static int[][][] dp = new int[2 * N * N][N][N];
    private static int[][] g;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(reader.readLine());
        int[][] graph = new int[n][];
        for (int i = 0; i < n; i++) {
            String[] s = reader.readLine().split("\\s+");
            int[] v = new int[s.length];
            for (int j = 0; j < s.length; j++) v[j] = Integer.parseInt(s[j]);
            graph[i] = v;
        }
        writer.write(catMouseGame(graph) + "\n");
        writer.flush();
    }

    public static int catMouseGame(int[][] graph) {
        g = graph;
        n = graph.length;
        //初始化，都设置为无效值
        for (int i = 0; i < 2 * n * n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) dp[i][j][k] = -1;
            }
        }
        return dfs(0, 1, 2);
    }

    private static int dfs(int k, int i, int j) {
        //老鼠跑进了洞里面，老鼠获胜
        if (i == 0) return dp[k][i][j] = 1;
        //老鼠和猫相遇，猫获胜
        if (i == j) return dp[k][i][j] = 2;
        if (k >= 2 * n * n) return dp[k][i][j] = 0;
        //此时的状态是-1，需要更新，如果是偶数回合，老鼠行动；如果是奇数回合，猫行动，双方都是朝着自己获胜的趋势，若不能获胜则尽量平局，最后才是失败
        int result = dp[k][i][j];
        if (result != -1) return result;
        if ((k & 1) == 0) {
            //老鼠行动的回合，可以跑到i节点的所有邻节点，但是我们会优先选择能赢的点
            boolean win = false, draw = false;
            for (int v : g[i]) {
                int res = dfs(k + 1, v, j);
                if (res == 1) win = true;
                else if (res == 0) draw = true;
                if (win) break;
            }
            if (win) result = 1;
            else if (draw) result = 0;
            else result = 2;
        } else {
            //猫的回合
            boolean win = false, draw = false;
            for (int v : g[j]) {
                if (v == 0) continue;
                int res = dfs(k + 1, i, v);
                if (res == 2) win = true;
                else if (res == 0) draw = true;
                if (win) break;
            }
            if (win) result = 2;
            else if (draw) result = 0;
            else result = 1;
        }
        return dp[k][i][j] = result;
    }
}
